NAND flash storage systems have been widely adopted as storage devices in real-time embedded systems due to their small size, low power consumption, high density and good shock resistance. A typical NAND flash storage system usually includes two layers, the flash translation layer (FTL) and the memory technology device (MTD) layer. In NAND flash storage systems, page is the basic unit for read and write operations and block is the basic unit for erase operations. A block may contain a plurality of pages. The MTD layer provides primitive functions such as read, write, and erase that directly operate on the flash memory system. The FTL emulates the flash memory system as a block device so that the file system can access the flash memory transparently.
The FTL usually includes three components: an address translator, a garbage collector, and a wear-leveler. In an FTL, the address translator translates addresses between logical addresses and physical addresses based on a mapping table; the garbage collector reclaims space by erasing obsolete blocks with invalid data; the wear-leveler is an optional component that distributes write and erase operations evenly across all blocks so as to improve the lifetime of a flash memory system.
One of the major functions of an FTL is to perform garbage collection which is needed to reclaim space in NAND flash storage systems. During a garbage collection operation, a victim block's valid pages are copied (read out and written to) to a free block, and then the victim block is erased for reuse. Compared to read/write operations NAND flash storage system, a garbage collection operation takes much longer time to copy valid pages from a victim block to a free block and then erase the victim block. Garbage collection may have an adverse impact on the worst-case scenario system performance of real-time NAND flash storage systems. As a result, garbage collection optimization in NAND flash storage system is important because the worst system latency in a NAND flash storage system is determined by the performance of the garbage collection. Accordingly, garbage collection should only be triggered when the NAND flash storage system is out of free space. In addition, garbage collection optimization should not introduce excessive overhead to the average system performance of the NAND flash storage system.
In conventional garbage collection schemes, a large number of unnecessary erase operations are introduced because garbage collection is triggered at an early stage. As a result, the average system performance is deteriorated. Conventional garbage collection schemes in NAND flash cause deadline-misses in real-time embedded systems. In addition, the space overhead of conventional distributed partial garbage collection is excessive. The conventional distributed partial garbage collection does not completely solve the average performance degradation issue arising from the early stage garbage collections.
In order to solve the problems associated with conventional garbage collection schemes, a real-time garbage collection scheme is proposed to reduce the worst case scenario execution time of garbage collection. Over-provisioning is applied to map a small logical space (the capacity that users are able to see and use) to a big physical space (the capacity that a NAND flash storage system really has). Because multiple physical pages are mapped to one logical page, a certain amount of invalid pages will exist in the block. Due to over-provisioning, the number of valid page copies can be guaranteed to be less than a predetermined value based on an over-provisioning ratio. As a result, the worst-case execution time of garbage collection can be reduced. The execution time of garbage collection is relatively long because both valid-page copying and block erasing operations are performed in one garbage collection operation.